28090번 - 특별한 한붓그리기

문제

SCSC 동아리방에서 알고리즘을 재미있게 공부하던 뉴비와 고인물은 동아리방 구석에서 이분 그래프 $H$를 발견하였다! $H$는 $A$와 $B$로 나눌 수 있으며, $A$와 $B$에 존재하는 정점의 수가 $N$으로 같다는 사실을 알아낸 뉴비와 고인물은 이 이분 그래프로 "특별한 한붓그리기"라는 게임을 하기로 하였다. 이 게임은 뉴비와 고인물 두 명이서 다음과 같이 진행하며 $A$의 $i$번 정점은 $A_i$로, $B$의 $j$번 정점은 $B_j$로 표기한다.

1. 뉴비가 $A$에서 임의의 한 정점 $A_i$를 선택한다.
2. 고인물은 $B$에서 $A_i$과 연결되어 있는 정점들 중 임의의 한 정점인 $B_j$을 선택하고, $A_i$와 $B_j$를 연결하는 선을 긋는다. 만약 정점을 선택할 수 없다면 고인물이 패배한다.
3. 뉴비는 $A$에서 $B_j$와 연결되어 있는 정점들 중 임의의 한 정점인 $A_k$를 선택하고, $B_j$와 $A_k$를 연결하는 선을 긋는다. 만약 정점을 선택할 수 없다면 뉴비가 패배한다.
4. 게임이 종료될 때까지 2-3을 반복한다. 모든 정점은 최대 1번만 선택할 수 있다.

고인물은 이미 고일대로 고여 모든 순간에 최적의 판단을 한다는 것을 알고 있는 뉴비는 자신이 이길 가능성이 있긴 한 것인지 궁금해졌다. 뉴비의 궁금증을 해결해 주자!

입력

첫째 줄에 정점의 개수 $N,ドル 그 밑에 오는 줄 수 $L$이 공백으로 구분되어 주어진다. $(1 \le N \le 450; 1 \le L \le \min(N^2,2000))$ 둘째 줄부터 $L$개의 줄에 걸쳐 $A_s$와 $B_e$를 연결하는 간선에 대한 정보가 s e의 형식으로 주어진다. $(1 \le s,e \le N)$

동일한 간선이 2번 이상 주어지지 않으며, 입력으로 주어지는 모든 수는 정수이다.

출력

뉴비와 고인물이 서로 최적의 방법으로 게임을 진행할 때, 승리하는 사람이 고인물이라면 Oldbie를, 뉴비라면 Newbie를 출력한다.

제한

힌트