30288번 - Rally 서브태스크스페셜 저지다국어

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 ≤ N ≤ 5 000
• 0 ≤ M ≤ 500 000
• M ≤ N(N - 1)/2