날씨 - 도로망

이미지 출처: vegagerdin.is

아이슬란드 도로청이 다른 프로젝트와 관련하여 다시 여러분에게 연락했다. 현재 악천후에도 불구하고 많은 아이슬란드인이 전국을 여행하고 있다. 따라서 현재 상황에서 Kópavogur에서 Egilsstaðir까지 갈 수 있는지와 같은 문의가 도로청에 자주 들어온다.

도로청은 아이슬란드의 모든 도로를 설명하는 도로망 정보를 제공한다. 각 도로는 두 끝점과 풍속 임계값으로 설명된다. 풍속이 도로의 풍속 임계값보다 작거나 같으면 도로가 개방되어 그 도로로 이동할 수 있고, 그렇지 않으면 도로가 폐쇄된다.

이제 이러한 문의에 답할 수 있는 프로그램을 작성해야 한다. 각 문의에는 출발 위치, 도착 위치, 그리고 전국의 풍속에 관한 정보가 포함된다. 개방된 도로만을 이용하여 출발 위치에서 도착 위치까지 가는 경로가 존재하면 답은 Jebb여야 한다. 그렇지 않으면 답은 Neibb여야 한다.

점수

그룹 | 점수 | 제한

1 | 10 | $1 \leq n, q \leq 20$, 문의는 풍속의 내림차순으로 주어지며, 도로망은 순환 도로를 나타내는 하나의 사이클을 이루고

                                   교차로는 오름차순으로 연결된다($1$과 $2$, $2$와 $3$, ...). 그리고 $n$과 $1$이 연결된다.

2 | 30 | $1 \leq n, q \leq 100$, 문의는 풍속의 내림차순으로 주어진다.

3 | 20 | $1 \leq n \leq 250$, 문의는 풍속의 내림차순으로 주어진다.

4 | 30 | 문의는 풍속의 내림차순으로 주어진다.

5 | 10 | 추가 제한이 없다.

입력의 첫 번째 줄에는 세 정수 $n$ ($1 \leq n \leq 10^5$), 교차로의 수, $m$ ($0 \leq m \leq 10^5$), 도로의 수, 그리고 $q$ ($1 \leq q \leq 10^5$), 문의의 수가 주어진다.

이어서 $m$개의 줄이 주어지며, $i$번째 줄은 번호가 $i$인 도로를 설명한다. 각 줄에는 세 정수 $u_i$ ($1 \leq u_i \leq n$)와 $v_i$ ($1 \leq v_i \leq n$), 도로의 두 끝점, 그리고 $t_i$ ($0 \leq t_i \leq 10^9$), 도로의 풍속 임계값이 주어진다.

마지막으로 $q$개의 줄이 주어지며, $j$번째 줄은 번호가 $j$인 문의를 설명한다. 문의에 하나씩 차례대로 답하도록 보장하기 위해 문의는 암호화되어 있다. 따라서 각 줄에는 암호화된 세 정수 $a'_j$, $b'_j$, $h'_j$가 주어진다. 지금까지 Jebb라고 답한 문의의 수를 $x$로 나타낸다. $a_j, b_j$와 $h_j$의 올바른 값을 얻으려면 대부분의 프로그래밍 언어에서 $\hat{}$ 연산자로 표기되는 XOR 연산을 적용해야 하므로, 다음과 같다.

• $a_j = a'_j \hat{} x$,

• $b_j = b'_j \hat{} x$,

• $h_j = h'_j \hat{} x$.

따라서 각 문의에는 세 정수 $a_j$ ($1 \leq a_j \leq n$), 출발점, $b_j$ ($1 \leq b_j \leq n$, 도착점, 그리고 $h_j$ ($0 \leq h_j \leq 10^9$), 풍속이 포함된다.

각 문의마다 주어진 출발점에서 주어진 도착점까지 폐쇄된 도로를 전혀 포함하지 않는 경로가 존재하면 Jebb, 그러한 경로가 존재하지 않으면 Neibb 중 하나를 출력한다.