eolymp
bolt
Try our new interface for solving problems
Problems

Excursion

Excursion

Time limit 1 second
Memory limit 256 MiB

A group of n people decided to go on an excursion. During the tour they can visit some of the m cities.

The guide asked each person to express their wishes about visiting cities. Each person can say about some cities that he wants to visit by all means, and about some other cities - that he definitely does not want to visit.

The group always travels together. If a group drives into a city, then all the people who say that they definitely do not want to visit it are upset. If the group does not enter the city, then all the people who say that they want to visit it are upset.

The guide understands that it is not always possible to satisfy all wishes. She wants to make a plan so that each person gets upset no more than once.

Help the guide to cope with this difficult task and make a plan for visiting cities or find out that it is impossible.

Input data

The first line contains three integers n, m, k - the number of people, the number of cities and the number of wishes (1n, m, k10^5).

Each of the following k lines contains two integers a and b denoting wishes (1an, 1 ≤ |b| ≤ m). If b > 0, then the person number a wants to visit the city number b. If b < 0, then the person numbered a does not want to visit the city numbered -b. Each wish is indicated in the entry no more than once, for none of the participants there is no wish to visit and not visit the same city at the same time.

Output data

If there is no solution, then output -1.

Otherwise, on the first line print a single integer k - the number of cities that will be included in the plan.

On the second line print k integers - the numbers of cities to be visited. The numbers of the cities can be printed in any order.

If there are several possible answers, print any of them. Please note that you do not need to search for the maximum or minimum k, you can print any correct answer.

Examples

Input example #1
3 5 6
1 2
1 3
1 -4
2 3
2 4
2 5
Output example #1
3
2 3 5 
Input example #2
3 3 6
1 -1
1 2
2 -2
2 3
3 -3
3 1
Output example #2
0
Source 2018, XXVI Командный чемпионат школьников Санкт-Петербурга по программированию, October 18, Problem B