Ledger Validity Verification

Little Blue has recently developed a new way of accounting. In this system, a ledger is a collection of transaction records. Each transaction record has a unique transaction identifier \(txId\) whose magnitude indicates the chronological order (a transaction with a smaller \(txId\) occurs before a transaction with a larger \(txId\)). Each transaction record contains one or more input entries and one or more output entries.

An input entry refers to an output of a previous transaction. It is described by two numbers: \(fromTxId\) and \(fromTxOutNumber\) (with \(fromTxOutNumber=0,1,2,\dots\)). An output entry is specified by an account number \(account\) and a value \(val\), which means that \(val\) units of money are transferred to the account numbered \(account\). Note that when both \(fromTxId\) and \(fromTxOutNumber\) are \(-1\), the transaction is a special transaction, generated directly from the system account. A special transaction contains exactly one input and one output. Since the system account has an infinite supply of money, a special transaction always succeeds.

A ledger is legal if the following conditions hold:

1. For each transaction record, the total money amount in its inputs equals the total money amount in its outputs.
2. For a normal transaction (i.e. non-special transaction), an output, if used, must be used entirely by a single input (it cannot be split among multiple inputs). (Special transactions are excluded from this requirement.)
3. Transactions occur in sequence. In other words, a transaction cannot reference an output from a transaction that has not yet occurred (i.e. a transaction can only refer to outputs from transactions with a smaller \(txId\)).

You are given a ledger with \(N\) different accounts (numbered from 0 to \(N-1\)), all of which initially have a balance of 0, and \(M\) transactions recorded in the order of occurrence. Determine if the ledger is legal.

Note: For special transactions, the input will always be \(-1 -1\) and there will be exactly one input and one output.

inputFormat

The first line contains two integers \(N\) and \(M\) (the number of accounts and transactions, respectively). Then \(M\) transactions follow. Each transaction is given in the following format:

inputs_count outputs_count
fromTxId_1 fromTxOutNumber_1
fromTxId_2 fromTxOutNumber_2
... (total inputs_count lines)
account_1 val_1
account_2 val_2
... (total outputs_count lines)

For a special transaction, inputs_count and outputs_count are both 1, and the only input line will be "-1 -1".

outputFormat

Output a single line containing either true if the ledger is legal, or false otherwise.

sample

3 3
1 1
-1 -1
0 100
1 2
0 0
0 50
1 50
2 1
1 0
1 1
2 100

true