Network Infection

Problem Description
You have to determine if a computer virus can spread through a network to reach a specific target computer. There are $N$ computers in the network, numbered $1, 2, \dots, N$. You are given a list of $M$ two-way network cables, where each cable connects a pair of computers.

The virus starts on computer 1. If a computer gets infected, it will spread the virus to all other computers directly connected to it by a network cable.

Input Specification
The first line of the input will be an integer $N$ ($2 \le N \le 100\,000$). The second line of the input will be an integer $M$ ($0 \le M \le 100\,000$). The next $M$ lines each contain two positive integers $u$ and $v$ ($1 \le u, v \le N$), representing a two-way cable connecting computer $u$ and computer $v$. It is guaranteed that a cable will not connect a computer to itself.

• For 3 of the 15 available marks, $N \le 10$ and $M \le 10$.
• For an additional 4 of the 15 available marks, $M = N - 1$ and each computer is connected to at most 2 other computers (the network forms a single straight line).
• For an additional 4 of the 15 available marks, $N \le 1\,000$ and $M \le 1\,000$.
• For the remaining 4 marks, no further constraints apply.

Output Specification
Output yes if the virus can reach computer $N$. Otherwise, output no.

Sample Input 1

Output for Sample Input 1

Explanation of Output for Sample Input 1

The virus starts at computer 1. It spreads to computer 2 through the connection $(1,2)$. From computer 2, it spreads to computer 3 through the connection $(2,3)$. However, there are no cables connecting infected computers (1, 2, or 3) to computer 4 or computer 5. Therefore, the virus cannot reach the target, computer 5.

Sample Input 2

Output for Sample Input 2

Explanation of Output for Sample Input 2

Starting at computer 1, the virus can spread directly to computer 3. From computer 3, it spreads to computer 6. Even though there are other connections in the network, reaching the target computer 6 is possible, so the output is yes.

Notes
The online grader begins by testing submissions using the sample input. All other tests are skipped if the sample test is not passed.

For the final subtask (worth 4 marks), if you are using Python, you might encounter a RecursionError due to the default recursion depth limit. If you are implementing a recursive DFS, you can increase this limit by importing the sys module and using sys.setrecursionlimit(200000). Alternatively, you can implement DFS iteratively using a stack.