Viện dưỡng lão

View as PDF

Submit solution

Points: 100
Time limit: 1.0s
Memory limit: 266M
Input: stdin
Output: stdout

Problem type
Allowed languages
C++, Pascal, pypy3, Python

Trong một viện dưỡng lão, có N cụ già đang xem truyền hình. Chương trình truyền hình bao gồm M kênh, được đánh số từ 1 đến M. Mỗi cụ già có một kênh yêu thích và một kênh ghét riêng.

Nếu truyền hình đang hiển thị kênh mà một cụ ghét, cụ đó sẽ đứng dậy, từ từ đi đến TV, chuyển kênh sang kênh yêu thích của mình và quay lại ghế ngồi thoải mái. Nếu có nhiều cụ ghét kênh hiện tại, cụ trẻ nhất (cụ còn trẻ, không phiền) sẽ đứng lên đổi kênh, còn các cụ khác sẽ ngồi yên.

Tuy nhiên, sau khi một kênh được thay đổi, có thể lại có một cụ khác ghét kênh mới, và cụ đó sẽ tiếp tục thay đổi kênh. Vì các cụ rất cứng đầu, quá trình này có thể tiếp diễn mãi mãi.

Cho danh sách kênh yêu thích và kênh ghét của các cụ, cùng với kênh ban đầu của TV, hãy xác định số lần thay đổi kênh để tất cả các cụ đều hài lòng và ngồi yên.

Input:

  • Dòng đầu tiên chứa ba số nguyên N, M, và P (1 \leq N, M \leq 10^5, 1 \leq P \leq M), tương ứng là số lượng cụ già, số lượng kênh truyền hình và kênh ban đầu đang được hiển thị trên TV.

  • Mỗi trong N dòng tiếp theo chứa hai số nguyên a_ib_i (1 \leq a_i, b_i \leq M, a_i \neq b_i), tương ứng là kênh yêu thích và kênh ghét của cụ già thứ i. Thứ tự các cụ trong đầu vào được sắp xếp từ trẻ nhất đến già nhất.

Output:

  • Dòng đầu ra duy nhất chứa số lần thay đổi kênh cần thiết để tất cả các cụ đều hài lòng và ngồi yên. Nếu các thay đổi tiếp diễn mãi mãi, in ra -1.

Example:

Sample Input 1

3 4 2
1 2
2 3
3 2

Sample Output 1:

1

Sample Input 2:

3 3 1
1 2
2 3
3 1

Sample Output 1:

-1

Note:

  • Ban đầu, TV đang chiếu kênh số 2. Kênh này khiến cả cụ trẻ nhất và cụ già nhất cảm thấy khó chịu. Vì vậy, cụ trẻ nhất sẽ đứng lên một cách nhiệt tình và đổi kênh sang kênh 1, để mọi người đều có thể cùng xem kênh mà họ yêu thích.

Comments

There are no comments at the moment.