Ríkjafræði 2

이미지 출처: commons.wikimedia.org

Jörmunrekur는 범주론을 제법 이해하게 되었다고 생각했지만, 갑자기 더 깊이 살펴보기 시작하자 상황이 복잡해졌다! 범주론에서는 정리나 정의를 시각적으로 보조하기 위해 도식을 자주 사용한다. 도식은 보통 대상들과 그 대상들 사이의 화살표로 이루어진 범주를 나타낸다. Jörmunrekur가 지난번에 범주를 살펴본 이후 더 복잡해진 점은, 이제 $x$에서 $y$로 향하는 화살표가 있더라도 $y$에서 $x$로 향하는 화살표도 있다는 보장은 없다는 것이다. 양방향으로 이동할 수 있다면 각 방향으로 하나씩, 두 개의 별도 화살표로 주어져야 한다. 하지만 Jörmunrekur는 이에 굴하지 않고, 직접 도식을 몇 개 그려 보면 이 현상을 더 잘 이해할 수 있을 것이라고 생각한다. 처음에 도식에는 대상을 나타내는 몇몇 점만 있고 화살표는 없다.

채점

그룹 | 점수 | 제약 조건

1 | 40 | $1 \leq q \leq 1\,000$.

2 | 30 | $1 \leq q \leq 500\,000$, 화살표들은 절대로 사이클을 이루지 않는다.

3 | 30 | $1 \leq q \leq 500\,000$.

입력은 두 양의 정수 $n$과 $q$가 주어지는 한 줄로 시작한다. 여기서 $n$은 대상의 수이고 $q$는 입력에 주어지는 질의의 수이다. 대상에는 $1$부터 $n$까지 번호가 매겨지며, 항상 $1 \leq n \leq 1\,000$가 성립한다. 다음으로 각각 공백으로 구분된 세 정수 $o, x, y$가 주어지는 $q$개의 줄이 이어진다. $o$은 항상 $0$ 또는 $1$이며, $1 \leq x, y \leq n$이다. $o = 0$이면 이 질의는 Jörmunrekur가 대상 $x$에서 대상 $y$로 향하는 화살표를 그린다는 뜻이다. $o = 1$이면 Jörmunrekur는 $x$에서 시작해 $y$로 가는 어떤 화살표의 연속이 있는지 궁금해한다.

$1$으로 시작하는 각 질의마다 한 줄을 출력한다. $x$에서 $y$까지 어떤 화살표의 연속을 따라가는 것이 가능하면 Jebb을 출력한다. 그렇지 않으면 Neibb을 출력한다.

입출력의 크기가 상당히 크다. 충분히 빠른 I/O 방식을 사용해야 한다.