Time Limit:  10 s      Memory Limit:   128 MB
Submission:4     AC:0     Score:99.98


Classification levels like Secret and Top Secret are well-known features of military documents. Less well known are integrity levels, which correspond to how reliable information is.

In the Dynamic Biba integrity model, every user and every document is assigned an integrity level. If a user writes to a document that has a higher integrity level than the user does, the document’s integrity level goes down. Similarly, if a user reads a document that has a lower integrity level than the user does, the user’s integrity level goes down.

Your job is to keep track of the integrity levels of a number of users and documents. Complicating the matter is the fact that integrity levels aren’t simply numbers; a document might contain very trusworthy information about operations in Afganistan, while at the same time containing less trustworthy information about operations in Iraq.

Integrity levels are speficied by arbitrary labels, along with rules of the form AB, indicating that integrity level A is at most as trustworthy as integrity level B. The rules satisfy a number of conditions:

You will be given as input the labels and rules defining the integrity levels, as well as the initial integrity level of a number of users and a number of documents. The format will be as follows:


Please Input Input Here


Please Input Output Here


9 11 2 3 5 6 9 2 6 9 4 7 5 3 8 7 2 5 3 8 4 5 1 6 1 1 8 4 2 5 9 8 1 reads 3 1 writes 2 2 reads 2 1 reads 1 2 writes 1
8 6 2 5 7