Book Recommendation System

An online bookstore wants to implement an automated recommendation system that suggests a new book for each user. Each user has a reading history given as a list of (user, book) pairs. The recommendation for a user is based on the following idea:

For a given user \(i\) with a reading list \(R_i\), consider every other user who has read at least one book from \(R_i\). For every book that user \(j\) has read and that user \(i\) has not read, we add a vote. The recommended book for user \(i\) is the one with the highest vote count. In case of a tie, choose the book with the smallest identifier. If user \(i\) has already read all books, output \(-1\).

This system is useful to capture similarities in reading tastes among users.

inputFormat

The input is read from standard input (stdin) and is structured as follows:

• The first line contains two integers \(N\) and \(M\), the number of users and the number of books respectively.
• The second line contains an integer \(K\), representing the number of records in the reading history.
• The next \(K\) lines each contain two integers: a user identifier and a book identifier, indicating that the user has read that book.

Note: Users and books are numbered starting from 1.

outputFormat

Output a single line to standard output (stdout) containing \(N\) integers separated by spaces. The \(i\)-th integer is the recommended book for user \(i\). If no recommendation can be made for a user, output \(-1\) for that user.

3 5
7
1 1
1 2
2 2
2 3
3 1
3 4
3 5

3 1 2