A common problem faced by programmers is the need to reuse dynamically allocated memory when it is no longer needed. One approach is to automatically detect such pieces of unusable memory (garbage) by tracking program pointers. This technique, known as garbage collection, is used in languages such as Lisp and Java.
As a systems programmer, it is your job to track statements
executed by a program and determine what memory may be reused.
All memory is allocated as cells which contain
two pointers each ( 
). Cell pointers initially point nowhere, but
may be pointed at specific cells through assignment statements.
A cell is considered to be garbage when it can no longer be accessed by a pointer from cell 1 (the main program's cell), or through a pointer from some cell accessible from cell 1. Cell 1 is never considered to be garbage. Your job is to track a number of assignment statements to cells, then decide which cells are garbage and may be reused.
The first line of input will be n, the number of cells. The cells are numbered from 1 to n. Remaining lines will be a list of ordered triples (x,y,z) specifying an assignment of cell x's pointer y to cell z. The list is terminated by a triple where x = 0. You may assume there are a maximum of 50 cells.
The output consists of one line. Output ``Garbage cells: " and the list of garbage cells found, in order from lowest to highest.
Input:
3 1 1 2 2 1 1 2 1 2 0 0 0
Output:
Garbage cells: 3
Input:
8 1 1 2 1 2 7 2 1 6 1 2 5 3 1 4 4 1 3 0 0 0
Output:
Garbage cells: 3 4 7 8
| Input 1 | Output 1 |
|---|---|
| Input 2 | Output 2 |
| Input 3 | Output 3 |
| Input 4 | Output 4 |
| Input 5 | Output 5 |
| Input 6 | Output 6 |