import java.io.*; import java.util.*; import java.awt.geom.*; /** * Solution to Gears * * @author vanb */ public class gears_vanb { public Scanner sc; public PrintStream ps; /** * This is a "Move" in the breadth-first search. * @author vanb */ public class Move { /** The gear we're moving to */ public int gear; /** * The direction it should be spinning: * 1 = same direction as the source gear * -1 = opposite direction from the source gear * 0 = We haven't reached this gear from the source gear */ public int direction; /** * Build a Move. * * @param gear Gear number * @param direction Direction it's spinning */ public Move( int gear, int direction ) { this.gear = gear; this.direction = direction; } } /** * This holds all of the pertinent info for a gear. * * @author vanb */ public class Gear { /** x,y coordinates */ public int x, y; /** Radius */ public int r; /** Direction it's spinning (See 'Move' above) */ public int direction; /** Other gears it meshes with */ public LinkedList edges = new LinkedList(); /** * Build a Gear. * * @param x X coord of center * @param y Y coord of center * @param r Radius */ public Gear( int x, int y, int r ) { this.x = x; this.y = y; this.r = r; this.direction = 0; } } /** * Greatest common Divisor, using Euler's technique. * * @param a An integer * @param b Another integer * @return The Greatest Common Divisor of a and b */ public int gcd( int a, int b ) { return b==0 ? a : gcd( b, a%b ); } /** * Driver. * @throws Exception */ public void doit() throws Exception { sc = new Scanner( System.in ); ps = System.out; int n = sc.nextInt(); Gear gears[] = new Gear[n]; for( int i=0; i q = new LinkedList(); q.add( new Move( 0, 1 ) ); while( free && !q.isEmpty() ) { Move m = q.removeFirst(); // If we haven't visited this gear yet, then // set its direction and go to its neighbors. if( gears[m.gear].direction==0 ) { gears[m.gear].direction = m.direction; for( int i : gears[m.gear].edges ) { q.add( new Move( i, -m.direction ) ); } } else { // If we have visited it, make sure // it's turning in the right direction. free = gears[m.gear].direction == m.direction; } } // If free is false, then the source gear cannot turn freely. if( !free ) ps.println( -1 ); // If the target gear's direction hasn't been set, then we can't reach it. else if( gears[n-1].direction==0 ) ps.println( 0 ); else { // Otherwise, the turning ratio is just based on the radii. int factor = gcd( gears[0].r, gears[n-1].r ); int a = gears[n-1].r / factor; int b = gears[0].r / factor * gears[n-1].direction; ps.println( a + " " + b ); } } /** * @param args */ public static void main( String[] args ) throws Exception { new gears_vanb().doit(); } }