경찰과 강도

바이트모어 시의 골목은 길모퉁이와 길모퉁이를 잇는다. 강도 사건이 일어나면 순찰 중이던 경찰관 한 명이 혼자서 강도를 쫓는다. 경찰은 추격을 컴퓨터로 계획하려고 도시 지도를 정확하게 만들었다.

경찰관 한 명이 강도 한 명을 쫓는 상황을 다음과 같이 정한다. 모퉁이에는 $1$번부터 $n$번까지 번호가 붙어 있고, 골목 하나는 서로 다른 두 모퉁이를 잇는다.

1. 경찰관이 순찰할 모퉁이를 하나 고른다.
2. 강도가 범행할 모퉁이를 하나 고른다. 강도는 경찰관이 어디 있는지 알고 고른다. 이때부터 두 사람은 서로의 위치를 항상 안다.
3. 경찰관은 한 번의 이동으로 골목이 이어진 이웃 모퉁이로 옮기거나, 옮기지 않고 그 자리에서 기다린다.
4. 강도는 한 번의 이동으로 골목이 이어진 이웃 모퉁이로 옮긴다. 경찰관과 달리 강도는 기다릴 수 없고 반드시 옮겨야 한다.
5. 경찰관부터 시작해 두 사람이 번갈아 한 번씩 이동하며, 다음 중 하나가 일어나면 멈춘다.
   1. 둘 중 누구의 이동이든 그 직후에 두 사람이 같은 모퉁이에 있으면 경찰관이 강도를 잡는다.
   2. 두 사람의 위치와 다음에 이동할 쪽이 모두 같은 상황이 다시 나타나면 강도가 달아난다. 강도가 경찰관을 언제까지나 피할 수 있다는 뜻이다.

강도가 경찰관과 같은 모퉁이를 고르면 이동 없이 그 자리에서 잡힌다.

이동 횟수는 경찰관의 이동과 강도의 이동을 모두 세고, 경찰관이 기다린 것도 한 번으로 센다. 경찰관은 강도를 잡는 것을 첫째 목표로 삼고, 잡을 수 있으면 이동 횟수를 가장 적게 만든다. 강도는 달아나는 것을 첫째 목표로 삼고, 어떻게 해도 달아날 수 없으면 이동 횟수를 가장 많게 만든다. 두 사람 모두 최선으로 움직인다.

도시 지도가 주어질 때, 경찰관이 강도를 반드시 잡을 수 있는지 판정하라.

첫째 줄에 모퉁이의 수 $n$과 골목의 수 $m$이 공백 하나로 구분되어 주어진다. 다음 $m$개 줄에는 골목 하나가 잇는 두 모퉁이의 번호 $a$와 $b$가 주어진다.

• $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$
• 같은 두 모퉁이를 잇는 골목은 두 번 이상 주어지지 않는다. $(a, b)$와 $(b, a)$는 같은 골목이다.
• 골목에는 방향이 없다. 어느 모퉁이에서 출발해도 골목만 따라가서 나머지 모든 모퉁이에 갈 수 있다.

강도가 어느 모퉁이를 고르더라도 경찰관이 반드시 강도를 잡을 수 있는 시작 모퉁이가 하나라도 있으면, 첫째 줄에 YES를 출력하고 둘째 줄에 그 시작 모퉁이의 번호와 이동 횟수를 공백 하나로 구분해 출력한다. 시작 모퉁이 $c$의 이동 횟수는 강도가 가장 오래 버티는 모퉁이를 골랐을 때 잡기까지 걸리는 이동 횟수이다. 이 값이 가장 작은 시작 모퉁이를 출력하고, 그런 모퉁이가 여럿이면 번호가 가장 작은 것을 출력한다.

그런 시작 모퉁이가 하나도 없으면 첫째 줄에 NO만 출력한다.