루미 알고리즘

#1643다이아Fredrik's Pizzeria

PO 2026 훈련 캠프코딩출제 Joshua Andersson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

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.

GroupPointsConstraints
15N, M ≤ 100 and there are no cycles.
210There are no cycles.
312N, M ≤ 100
48N, M ≤ 2000 and each room is part of at most one cycle.
515N, M ≤ 2000
619Each room is part of at most one cycle.
731No 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

출처 표기

출처: Programmeringsolympiaden 2026년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.