Cop and Robber

Time limit1.5sMemory limit256 MB

Summary

Decide if one starting corner lets the chasing officer force a catch on a connected graph and print the best corner with its worst-case move count.

Level: Medium7 of 10
Topics: Game theory, Graph, BFS
Solved: No attempts yet

Problem

Alleys in the city of Bytemore connect street corners. When a robbery happens, one patrolling police officer chases the robber alone. The police drew an exact map of the city so that a computer can plan the chase.

One officer chasing one robber works as follows. The corners are numbered $1$ through $n$ , and one alley joins two different corners.

The officer picks one corner to patrol.
The robber picks one corner for the robbery. He knows where the officer is when he picks. From that moment on, each one always knows where the other is.
On his move the officer walks to a corner joined to his own by an alley, or waits where he is.
On his move the robber walks to a corner joined to his own by an alley. Unlike the officer, the robber cannot wait and has to move.
Starting with the officer, the two take turns making one move each until one of the following happens.
1. Right after a move by either one, both stand on the same corner. The officer catches the robber.
2. A situation repeats, where a situation is the two positions together with the side that moves next. The robber then avoids the officer forever and escapes.

If the robber picks the corner the officer patrols, he is caught on the spot without any move.

The move count includes the moves of the officer and the moves of the robber, and a wait by the officer counts as one move. The officer's first goal is to catch the robber, and when he can, he makes the move count as small as possible. The robber's first goal is to escape, and when he cannot escape at all, he makes the move count as large as possible. Both play their best.

Given the map of the city, decide whether the officer can always catch the robber.

Input

The first line has the number of corners $n$ and the number of alleys $m$ , separated by one space. Each of the next $m$ lines has the numbers $a$ and $b$ of the two corners that one alley joins.

$1 \le n \le 100$
$0 \le m \le n(n-1)/2$
$1 \le a \le n$ , $1 \le b \le n$ , $a \ne b$
No alley between the same two corners is given twice. $(a, b)$ and $(b, a)$ are the same alley.
Alleys have no direction. From any corner you can reach every other corner along alleys.

Output

If at least one starting corner lets the officer catch the robber whatever corner the robber picks, print YES on the first line, then print the number of that starting corner and the move count on the second line, separated by one space. The move count of a starting corner $c$ is the number of moves the catch takes when the robber picks the corner he holds out on the longest. Print the starting corner whose move count is smallest, and among those the one with the smallest number.

If no such starting corner exists, print only NO on the first line.

Examples3

Example 1
Input
```
3 2
1 2
2 3
```
Expected output
```
YES
2 1
```
Example 2
Input
```
4 4
1 2
1 4
2 3
3 4
```
Expected output
```
YES
1 3
```
Example 3
Input
```
5 5
1 2
1 5
2 3
3 4
4 5
```
Expected output
```
NO
```