영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
Your friend Elsa works as a night guard at Fredrik's pizzeria. The pizzeria has N rooms and M undirected corridors, numbered from 1 to N and 1 to M respectively. She is currently in room 1. The night shift just ended, and she wants to go home through the exit in room 2. Unfortunately, there is a malicious rat in room 3 that is trying to stop her. To protect herself, each corridor has an electronic door that she can close. Neither Elsa nor the rat can pass through a closed door. She can open and close doors however she wants, with one requirement: each door is linked to exactly one other door. If two doors are linked, it means that if one is closed, the other must also be closed. Likewise, if one is open, the other must also be open. Doors being linked with each other is symmetric, which means that if door a is linked to door b, then door b is linked to door a.
Since the control panel is in her office in room 1, she must decide which corridors to open or close before leaving the office. Once she has left the office, her only chance is to have closed doors so that the rat cannot reach her through corridors with open doors, while she can reach the exit through corridors with open doors. Even if her office were right next to the exit, the rat is so fast that she would not be able to get out in time if the rat could reach her.
Determine whether there is a way to close doors so that Elsa can get out, while the rat cannot reach her.
Due to fire safety regulations, it is also guaranteed that each corridor is part of at most one cycle (The definition of a cycle with k (k ≥ 3) rooms is a sequence of rooms c_1, c_2, …, c_k, where all c_i are pairwise distinct and there is a corridor between c_i and c_{i+1}. Note that there must also be a corridor between c_k and c_1. In particular, a single room, or a pair of rooms connected by a corridor is not a cycle, since k < 3 in those cases.).
Input
The first line of input contains the integers N and M (3 ≤ N ≤ 2 · 10^5, 2 ≤ M ≤ 2 · 10^5), the number of rooms and corridors in the pizzeria. It is guaranteed that M is even.
The ith of the following M lines each contains the integers u, v and l (1 ≤ u,v ≤ N, u ≠ v, 1 ≤ l ≤ M, l ≠ i), meaning that there is a corridor between rooms u and v, and that this corridor is linked with corridor number l. The corridors are given in the same order as they are numbered. It is guaranteed that there is at most one corridor between each pair of rooms. It is also guaranteed that a corridor is linked with a different corridor and that the linking of corridors is symmetric: corridor l is linked with corridor i.
It is also guaranteed that all rooms can be reached from room 1 if all doors are open, and that each corridor is part of at most one cycle.
Output
Print “Ja” if it is possible to close doors so that Elsa can get out while the rat cannot reach her, otherwise “Nej”.
Scoring
Your solution will be tested on a set of test groups. To earn points for a group, you must pass all test cases in that group.
| Group | Points | Constraints |
|---|---|---|
| 1 | 5 | N, M ≤ 100 and there are no cycles. |
| 2 | 10 | There are no cycles. |
| 3 | 12 | N, M ≤ 100 |
| 4 | 8 | N, M ≤ 2000 and each room is part of at most one cycle. |
| 5 | 15 | N, M ≤ 2000 |
| 6 | 19 | Each room is part of at most one cycle. |
| 7 | 31 | No additional constraints. |
Explanation of Samples
All samples will be visualized as follows: room 1 (the starting room) will be marked green, room 2 (the exit) blue, and room 3 (the rat's room) red. The corridors will be colored so that corridors with the same color are linked.
In sample 1, it is not possible because the only corridors between the exit and the rat are linked. If Elsa chooses to open corridors 1 and 2, the rat will stop her. If she closes the corridors, she will not be able to get out.
(그림은 원문 저장소에서 볼 수 있습니다)
In sample 2, it is possible. One solution is to close the pairs of doors in corridors 2,7 and 4,5. Then the rat cannot reach Elsa, while she can get out by walking through rooms 1,4,6,2. This case could not be part of group 4 or 6 since room 6 is part of two cycles (the cycles 6,4,1,5 and 6,7,3).
(그림은 원문 저장소에서 볼 수 있습니다)
예제
예제 1
4 4 1 2 2 1 3 1 2 4 4 4 3 3
Nej
예제 2
7 8 1 4 6 1 5 7 4 6 8 5 6 5 6 7 4 7 3 1 3 6 2 6 2 3
Ja