번부터 번까지 번호가 붙은 명의 사람이 일렬로 서 있다. 거짓말쟁이들은 정확히 하나의 비어 있지 않은 연속 구간을 이룬다. 즉, 어떤 이 존재하여 번 사람만 거짓말쟁이이다.
번 사람은 번부터 번까지의 사람 중 적어도 한 명이 거짓말쟁이라고 주장한다.
거짓말쟁이의 주장은 거짓이고, 거짓말쟁이가 아닌 사람의 주장은 참이다.
현재 주장들과 모순되지 않는 거짓말쟁이 구간을 하나 구하여라. 그런 구간이 없다면 그 사실을 판별해야 한다.
사람들의 주장은 여러 번 변경된다. 각 변경 뒤의 주장들에 대해 답을 출력하여라.
Input
입력은 다음과 같은 형식으로 주어진다.
각 케이스는 다음과 같은 형식으로 주어진다.
번 변경에서는 번 사람의 주장을 번부터 번까지의 사람 중 적어도 한 명이 거짓말쟁이라는 주장으로 바꾼다. 즉, 를 로 변경한다.
Output
각 케이스의 각 변경 뒤에 한 줄을 출력한다.
현재 주장들과 모순되지 않는 거짓말쟁이 구간이 없다면 -1을 출력한다.
그런 구간이 있다면 두 정수 을 공백으로 구분하여 출력한다. 출력한 은 을 만족해야 하며, 정확히 번부터 번까지의 사람이 거짓말쟁이라고 할 때 모든 사람의 주장이 조건에 맞아야 한다.
가능한 답이 여러 가지라면 아무거나 출력해도 된다.
Constraints
- .
- .
- .
- ().
- ().
- ().
- 모든 테스트 케이스에 대한 의 합은 이하이다.
Subtasks
Samples
입력
1
4 4
1 2
2 2
1 3
1 3
1 2 3
2 1 4
2 1 3
1 2 3
출력
-1
1 1
1 1
1 1
첫 번째 변경 뒤에는 조건을 만족하는 거짓말쟁이 구간이 없다.
두 번째 변경 뒤에는 번 사람만 거짓말쟁이라고 할 수 있다. 이후 두 변경 뒤에도 같은 구간이 조건을 만족한다.