Cats and Dogs around the Table

View as PDF

Submit solution

Points: 100
Time limit: 2.0s
Memory limit: 512M

Author:
Problem type

problem header

You are hosting the annual convention for Cats & Dogs, an often ill fated and messy gathering. In order to crack down on cat fights and butt-sniffing, you've decided to take control of the seating arrangement for dinner.

Dinner will occur on multiple circular tables, with each seat at the table alternating between dog and cat. Easy enough right? While it is unlikely for dogs and cats to get along, there are a known list of certain cats and dogs which can sit amicably together, and cause little issues.

You are a master craftsman, and so can create as many arbitrarily sized circular tables as you'd like, provided the table seats at least 4 animals, but there should be no seat unused! Can you seat every dog and cat?

Input

Input will begin with three space-separated integers, C, D and P, the number of cats, dogs, and pairings of cats/dogs which can sit adjacent to one another. P lines follow, containing two integers x and y. This means that Cat #x can sit with Dog #y. (These are 1-indexed)

Output

Output a single YES or NO to tell whether there is some set of tables that can be made to seat everyone. If the answer is YES, output c lines, outlining which two dogs each cat is adjacent to, in order, in the following format: Cat #x sits with Dog #y and Dog #z

Constraints

  • 1 \leq C \leq 3000
  • 1 \leq D \leq 3000
  • 0 \leq P \leq 50000

Example Run

For the following input:

4 4 12
1 4
1 1
1 3
3 3
3 4
3 1
2 2
2 4
2 1
4 2
4 3
4 1

One possible answer is

YES
Cat #1 sits with Dog #1 and Dog #3
Cat #2 sits with Dog #2 and Dog #4
Cat #3 sits with Dog #4 and Dog #1
Cat #4 sits with Dog #2 and Dog #3

there are multiple possible solutions, another including 2 tables of size 4.


Comments


  • 0
    hmm  commented on Oct. 1, 2022, 3:14 p.m.

    half of my tests return with IR (invalid return). Does anybody know what that means? it's not listed as an output on the contest page.


    • 1
      admin  commented on Oct. 1, 2022, 3:16 p.m.

      Hi, You are getting a particular error raised (One that can only occur when your input is large)