← Home
package main

import (
	"io"
	"os"
	"strconv"
)

type Frac struct {
	n int64
	d int64
}

type Frame struct {
	v     int
	pEdge int
	idx   int
	pool  []int
}

func gcd(a, b int64) int64 {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func main() {
	data, _ := io.ReadAll(os.Stdin)
	pos := 0
	nextInt := func() int64 {
		for pos < len(data) && (data[pos] < '0' || data[pos] > '9') {
			pos++
		}
		var v int64
		for pos < len(data) && data[pos] >= '0' && data[pos] <= '9' {
			v = v*10 + int64(data[pos]-'0')
			pos++
		}
		return v
	}

	n := int(nextInt())

	idMap := make(map[Frac]int, 2*n)
	adj := make([][]int, 0, 2*n)

	getID := func(f Frac) int {
		if id, ok := idMap[f]; ok {
			return id
		}
		id := len(adj)
		idMap[f] = id
		adj = append(adj, nil)
		return id
	}

	eu := make([]int, n+1)
	ev := make([]int, n+1)

	for i := 1; i <= n; i++ {
		a := nextInt()
		b := nextInt()
		c := nextInt()
		d := nextInt()

		num1 := c * b
		den1 := d * (a + b)
		g1 := gcd(num1, den1)
		f1 := Frac{num1 / g1, den1 / g1}

		num2 := b * (c + d)
		den2 := a * d
		g2 := gcd(num2, den2)
		f2 := Frac{num2 / g2, den2 / g2}

		u := getID(f1)
		v := getID(f2)

		eu[i] = u
		ev[i] = v
		adj[u] = append(adj[u], i)
		adj[v] = append(adj[v], i)
	}

	visV := make([]bool, len(adj))
	visE := make([]bool, n+1)
	ans := make([][2]int, 0, n/2)
	stack := make([]Frame, 0, 64)

	for root := 0; root < len(adj); root++ {
		if visV[root] {
			continue
		}
		visV[root] = true
		stack = append(stack[:0], Frame{v: root, pEdge: -1})

		for len(stack) > 0 {
			top := len(stack) - 1
			if stack[top].idx < len(adj[stack[top].v]) {
				eid := adj[stack[top].v][stack[top].idx]
				stack[top].idx++
				if visE[eid] {
					continue
				}
				visE[eid] = true

				to := eu[eid]
				if to == stack[top].v {
					to = ev[eid]
				}

				if !visV[to] {
					visV[to] = true
					stack = append(stack, Frame{v: to, pEdge: eid})
				} else {
					stack[top].pool = append(stack[top].pool, eid)
				}
			} else {
				pool := stack[top].pool
				for len(pool) >= 2 {
					e1 := pool[len(pool)-1]
					e2 := pool[len(pool)-2]
					pool = pool[:len(pool)-2]
					ans = append(ans, [2]int{e1, e2})
				}

				pEdge := stack[top].pEdge
				usedParent := false
				if pEdge != -1 && len(pool) == 1 {
					ans = append(ans, [2]int{pool[0], pEdge})
					usedParent = true
				}

				stack = stack[:top]
				if len(stack) > 0 && pEdge != -1 && !usedParent {
					parent := len(stack) - 1
					stack[parent].pool = append(stack[parent].pool, pEdge)
				}
			}
		}
	}

	out := make([]byte, 0, 32+len(ans)*24)
	out = strconv.AppendInt(out, int64(len(ans)), 10)
	out = append(out, '\n')
	for _, p := range ans {
		out = strconv.AppendInt(out, int64(p[0]), 10)
		out = append(out, ' ')
		out = strconv.AppendInt(out, int64(p[1]), 10)
		out = append(out, '\n')
	}
	_, _ = os.Stdout.Write(out)
}