Log inSign up
Problems / B085

Substations that get the maintenance notice

200 ptsCases 15Set by dongbinna
Added October 30.
1 solved1 attempted1 submissionssolvers took 1.0 tries on average

Statement

A region's power grid has substations numbered from 1 to n. Some of the substations are joined by transmission lines, and electricity flows both ways along a transmission line. Several transmission lines may join the same two substations.

A large maintenance job has now been scheduled at substation 1. While the work goes on, the voltage at substation 1 swings, and the swing spreads along the transmission lines. The swing dies down once it has passed over two transmission lines, so only the substations reached over two or fewer transmission lines are affected.

The person in charge of the grid wants to send a maintenance notice to the affected substations in advance. Write a program that takes the transmission lines and finds how many substations the notice has to go to. Substation 1, where the work is done, is not counted.

For example, suppose there are n=6 substations and m=5 transmission lines, laid out as in the table below.

Transmission line12345
The two substations joined1, 21, 33, 42, 34, 5

The smallest number of transmission lines that have to be crossed from substation 1 to each substation is as follows.

Substation123456
Number of transmission lines crossed01123Not reached

Substation 2 and substation 3 are joined to substation 1 directly, so they cross one transmission line. Substation 4 has to go through substation 3, so it crosses two. Substation 5 has to cross one more after reaching substation 4, so it crosses three, and substation 6 is not joined to substation 1 at all.

The substations reached over two or fewer transmission lines are 1, 2, 3, and 4. Taking out substation 1, where the work is done, leaves 2, 3, and 4. The answer in this case is therefore 3.

Input and Output Examples

Example 1

Input

6
5
1 2
1 3
3 4
2 3
4 5

Output

3

Example 2

Input

3
2
3 1
3 2

Output

2

Example 3

Input

3
0

Output

0

Input

  • First the number of substations n is given as a natural number. (n is a natural number less than or equal to 500.)

  • Then the number of transmission lines m is given. (m is an integer from 0 to 10,000.)

  • Then m lines follow, each holding the numbers x and y of the two substations one transmission line joins, separated by a space. x and y are both natural numbers from 1 to n. If m is 0, not a single line of transmission line information is given.

Output

  • Print the number of substations the maintenance notice has to go to on one line. Count the substations reached from substation 1 over two or fewer transmission lines, and do not count substation 1 itself, where the work is done. Only one number is printed, so no space is left at the end of the line.

Requirements

  • A transmission line carries in both directions
  • Distance is counted as the number of transmission lines crossed. Only the substations at two or fewer get the notice
  • Leave substation 1 itself out of the answer
  • Do not count a substation that is not joined to substation 1
  • If there is not a single transmission line, the answer is 0
  • You must write a program that reads from standard input and writes to standard output
  • Trailing spaces at the end of a line and blank lines at the end of the output are ignored when grading
  • The languages you can use are Python and JavaScript
  • The memory limit is 256MB. The browser does not measure it, it only states it
  • The time limit is set by measuring the setter's reference solution on the same runtime
  • On this problem you submit code, not a prompt. That code runs in the browser on this device, and all that goes to the server is a fingerprint of the output and the time it took. Whether it is correct is decided by the server. The run time is a number each device reports, so the code and the device details are posted next to it on the leaderboard.
  • The output has to match the expected value down to the character. A space inside a line counts the same as any other character.
  • There are 15 cases, and 3 of them show the input together with the expected output. The rest are used only when you submit and are not shown on this page.
  • You have to pass all 15 cases to solve this.
Read the requirements carefully before solving. Tampering with the grading to make a submission look like a pass can get you sanctioned if caught. The code you submit is published on the leaderboard along with the result.

Examples

3 public cases. Judging also uses hidden cases. You have to pass all 15 cases to solve this.

Input
Expected output
3
2
3 1
3 2
2
3
0
0
6
5
1 2
1 3
3 4
2 3
4 5
3

Solution

Your code runs on this device. Only the fingerprint of the output and the elapsed time go to the server. The server decides whether it is correct.

0 chars1 lineMemory 256MB (recorded only)Reference 12ms

Submitting requires you to log in. Running against the public cases works without one.

You can test with 3 public cases. Submitting runs the hidden cases too.

People who solved this problem

The time shown is the time spent solving. Input reading time is outside the solver's control, so it is excluded. And since each device reports this value itself, we record which device measured it.

1bampal260ms315 charsPythonWindows NT 10.0 / Chrome/156.0.0.0 / 8코어 / 16GB

Log in and you can see the code once you solve this problem.