| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.5 초 | 1024 MB | 61 | 25 | 22 | 40.741% |
Byteland has N cities. Some of the cities are connected by roads.
Byteland rally organisers asked you to set up a track that would consist of exactly four roads and that would start and end in the same city. A road can not be added to the track more than once.
Figure 1: Four marked roads make a valid track
Knowing the road map of Byteland, set up a rally track.
The first line contains the number of cities N and the number of roads M. Cities are numbered from 1 to N.
The following M lines describe M roads. Each line contains 2 integers from 1 to N – the numbers of the cities the road connects.
Roads connect distinct cities, and any pair of cities is connected by at most one road.
If it is possible to set up a track, output TAIP on the first line. On the second line output four numbers – the city numbers the track goes through.
If several solutions are possible, output any of them.
If it is impossible to set up a track, output NE.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | 1 ≤ N ≤ 100 |
| 2 | 30 | 1 ≤ N ≤ 400 |
| 3 | 25 | 1 ≤ N ≤ 1 100 |
| 4 | 35 | 1 ≤ N ≤ 5 000 |
8 9 2 3 3 4 7 8 1 2 4 5 6 7 5 6 8 2 4 1
TAIP 4 3 2 1
Example is shown in the figure above. There are different possible solutions.
5 4 1 2 2 3 3 4 4 5
NE
It is impossible to set up a track.
Olympiad > Lithuanian Olympiad in Informatics > Lithuanian Olympiad in Informatics 2015/2016 > National Round (2) > 7-9 Classes 1번
Olympiad > Lithuanian Olympiad in Informatics > Lithuanian Olympiad in Informatics 2015/2016 > National Round (2) > 10-12 Classes 1번