Daisy Chains in the Field

Interview

Time limit1sMemory limit128 MB

Summary
Given an undirected graph of cows joined by ropes, list in ascending order every cow that cannot reach cow 1, or print 0 if all cows are connected to it.
Level

Easy3 of 10

Topics
Graph, DFS, BFS, Implementation
Solved
No attempts yet

Problem

Farmer John lets his NN (1≤N≤2501 \le N \le 250) cows, numbered 1…N1 \ldots N, play in the field. The cows tie themselves to one another with cow-ropes, forming MM (1≤M≤N(N−1)21 \le M \le \frac{N(N-1)}{2}) pairwise connections. No two cows are joined by more than one rope. Each connection is given as a pair of cows c1c_1 and c2c_2 (1≤c1≤N1 \le c_1 \le N; 1≤c2≤N1 \le c_2 \le N; c1≠c2c_1 \ne c_2).

Farmer John wants every cow to belong to the same chain as cow 11. Help him spot the misbehaving cows: report, in ascending order, the numbers of the cows that are not linked to cow 11 through one or more ropes (cow 11 is, of course, always linked to herself). If there are no misbehaving cows, output 00.

To illustrate, consider six cows with four connections:

    1---2  4---5
     \  |
      \ |      6
       \|
        3

Here cows 44, 55, and 66 are not linked to cow 11.

Input

  • Line 11: two space-separated integers, NN and MM.
  • Lines 2…M+12 \ldots M+1: line i+1i+1 describes rope ii with two space-separated integers c1c_1 and c2c_2, the two cows it connects.

Output

  • Output one integer per line: the numbers of the cows not linked to cow 11, in ascending order.
  • If every cow is linked to cow 11, output a single line containing 00.

Examples1

  1. Example 1

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