Moda na zwycięstwo

빈센티 씨는 예전에 드라마 Moda na zwycięstwo 의 연속된 여러 화를 본 적이 있습니다. 그가 특히 놀란 것은 등장인물들 사이의 복잡하게 얽힌 연애 관계로 드러나는 작가들의 대단한 상상력이었습니다. 관계가 워낙 빠르게 생기고 끝나서, 마지막으로 본 화에서는 줄거리를 거의 따라가지 못했습니다.

그가 알아낸 것은 이것뿐입니다. 그가 본 화들 안에서, 어떤 인물들의 사슬 $P_1, P_2, \dots, P_k$ (단, $k \ge 2$) 가 존재해서, $P_1$ 은 최소 한 화 동안 $P_2$ 와 사귀었고, $P_2$ 는 최소 한 화 동안 $P_3$ 와 사귀었으며, 이런 식으로 $P_k$ 까지 이어집니다. 게다가 $P_1$ 은 $P_k$ 의 부모였습니다.

그로부터 여러 해가 지났습니다. 빈센티 씨는 그것이 몇 화였는지 더는 기억하지 못하지만, 이번에는 줄거리를 따라갈 수 있을지 확인하려고 그 화들을 다시 보고 싶어 합니다.

드라마 속 모든 연애 관계의 이력과 누가 누구의 부모인지가 주어질 때, 위에서 설명한 상황이 일어날 수 있는 연속된 화 구간의 가장 짧은 길이를 구하세요 (임의의 $k \ge 2$ 에 대해).

연속된 화 구간이란 화 번호들의 한 구간을 뜻합니다. 어떤 사슬에서 이웃한 모든 쌍 $P_j$ 와 $P_{j+1}$ 이 그 구간에 속한 화 중 최소 한 화에서 서로 사귀고 있었고 $P_1$ 이 $P_k$ 의 부모라면, 그 상황은 그 구간 안에 들어맞습니다. 구간의 길이는 그 구간에 포함된 화의 개수입니다.

첫 줄에는 자연수 $L$, 즉 테스트 케이스의 수가 주어집니다. 이어서 각 테스트 케이스가 차례로 주어집니다.

각 테스트 케이스의 첫 줄에는 두 자연수 $N$ 과 $M$ 이 주어지며, 각각 등장인물의 수와 연애 관계의 수입니다 ($1 \le N \le 200$, $0 \le M \le 50000$).

다음 $N$ 줄에는 가족 관계가 주어집니다. (1부터 세어) $i$ 번째 줄에는 두 정수 $A_i$ 와 $B_i$ 가 있으며, 이는 인물 $i$ 의 부모입니다 (인물도 1부터 번호가 매겨집니다). 이 두 수 중 하나가 $-1$ 이면 그 부모는 드라마에 등장하지 않는 인물이므로 고려하지 않습니다. $A_i < i$ 와 $B_i < i$ 를 가정해도 됩니다.

다음 $M$ 줄에는 연애 관계가 주어집니다. 각 관계는 네 정수 $P$, $Q$, $S$, $K$ 로 주어집니다 ($1 \le P, Q \le N$; $1 \le S < K \le 10^9$). 이는 인물 $P$ 와 $Q$ 가 $S$ 화부터 $K$ 화까지 (양 끝 포함) 사귀었다는 뜻입니다. 어떤 두 인물도 동시에 두 개의 관계를 맺고 있지는 않았다고 가정해도 됩니다.

각 테스트 케이스마다, 설명한 상황이 나타나는 연속된 화 구간의 가장 짧은 길이를 한 줄에 출력하세요. 그런 구간이 없으면 NIE 라는 단어를 출력하세요.