Neko on a tour

View as PDF

Submit solution

Points: 0.20 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

After the COVID-19 pandemic was erased on the cat planet, its government deregulated social distancing. After a year of staying at home because of the pandemic, Neko has decided to go on a tour to Uwutopia city, a famous tourist city with stunning sights (and constructions inspired by cats - the dominating animal on this planet).

There are ~m~ locations in the city, numbered ~1~ to ~m~. Neko has contacted a travel agent, and learns that the company is organizing ~n~ tours, the ~i~-th tour of which will visit all locations numbered ~l_i~ to ~r_i~. Since he hasn't gone touring anywhere for a long time, he decided to take two tours at once! However, he thinks visiting the same place twice is boring; he wants his two tours do not have any common locations.

Help Neko find any pair of tours satisfying his need, or tell him there's no such pair. If there are more than one pair of such tours, you can tell Neko any of them.


The first line contains two integers ~n~ and ~m~ (~2 \le n \le 10^5~, ~1 \le m \le 10^9~) — the number of tours and the number of locations, respectively.

The ~i~-th line of the following ~n~ lines contains two integers ~l_i~ and ~r_i~ (~1 \le l_i \le r_i \le m~) — description of the ~i~-th tour.


If there is a satisfying pair of tours, in the first line output YES, in the second line output two integers ~i~ and ~j~ (~1 \le i, j \le n~, ~i \neq j~), the indices of the chosen tours. If there are more than one pair of such tours, you can print any.

Otherwise, output NO on a single line.


  • Subtask 1 (~15~ points): ~n = 2~, ~m \le 100~

  • Subtask 2 (~15~ points): ~n \le 1000~

  • Subtask 3 (~20~ points): No additional constraints

The total score for this problem is ~50~.

Sample Input 1

4 5
1 3
1 2
3 5
4 4

Sample Output 1

4 2

Sample Input 2

4 10
1 4
2 5
3 6
4 7

Sample Output 2


Sample Input 3

2 10
1 4
6 10

Sample Output 3

1 2

Sampe Input 4

2 10
1 5
5 10

Sample Output 4



In the first example, the pair of tours ~(1, 4)~, ~(2, 3)~, or ~(2, 4)~ are also valid answers.


Please read the guidelines before commenting.

  • -7
    trieuyanglake_1  commented on June 25, 2022, 3:59 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.