Ruby ソートされる部分とされない部分があります

こんにちは。
paizaのCランクレベルアップ問題でわからない部分があります。
テスト時にソートされる部分とされない部分があり、何が原因かがわかりません。
以下問題と自分が作ったコード、間違って出力されるケースの入力内容と出力内容になります。
よろしくお願いします。

引用テキスト

p 人のグループ A , q 人のグループ B , r 人のグループ C があります。各グループのメンバーにはそれぞれ番号がつけられており、 A グループの i 番目の人は B グループの j 番目の人に仕事を任せ、 B グループの j 番目の人は与えられた仕事を C グループの k 番目の人に任せます。すると結局、 A グループの i 番目の人の仕事をするのは C グループの k 番目の人だということになります。
パイザ君は A グループの各人の仕事を結局 C グループの誰が行うことになるのか知りたがっています。 A グループの人のそれぞれが最終的に C グループの誰に仕事を頼むことになるのかを、 A グループの人の番号が小さい順に p 行出力してください。

入力は以下のフォーマットで与えられます。

p q r
i_1 j_1
...
i_p j_p
j'_1 k_1
...
j'_q k_q

1 行目には A グループ、 B グループ、 C グループのそれぞれの人数 p , q , r が半角スペース区切りで与えられます。
2 行目から (p + 1) 行目までは A グループの人の番号とその人が仕事を頼む B グループの人の番号 i_a, j_a （1 ≤ a ≤ p）が半角スペース区切りで、 (p + 2) 行目から (p + q + 2) 行目までは B グループの人の番号とその人が仕事を頼む C グループの人の番号 j’_b , k_b （1 ≤ b ≤ q）が半角スペース区切りで与えられます。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください
期待する出力
A グループの i_c 番目の人が C グループの k_c 番目の人に仕事を頼むとしたとき（1 ≤ c ≤ p）、各 i_c, k_c をそれぞれ半角スペース区切りで、 i_c が小さい順に p 行出力してください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件
すべてのテストケースにおいて、以下の条件をみたします。

・1 ≤ p , q , r ≤ 50
・1 ≤ i_a ≤ p , 1 ≤ j_a , j'_b ≤ q , 1 ≤ k_b ≤ r （1 ≤ a ≤ p , 1 ≤ b ≤ q）
・各 i_a は全て異なる
・各 j'_b は全て異なる

A グループから仕事を頼まれた B グループの人は必ずその仕事を C グループの誰かに頼みます。 B グループに関する入力には「余計な」ものも含まれます。すなわち、 A グループの誰からも仕事を頼まれていない B グループの人に関して、その人が C グループの誰に仕事を頼むかについての情報が与えられることもあります。

入力例1
2 2 2
2 1
1 2
1 1
2 2

出力例1
1 2
2 1

入力例2
2 3 4
1 3
2 1
2 3
3 3
1 4

出力例2
1 3
2 4

Ruby
1n=gets.split(" ").map(&:to_i)
2line=readlines
3p=n[0]
4q=n[1]
5r=n[2]
6i=0
7hash1={}
8hash2={}
9
10#A→Bの辞書を作る
11while i<p
12    line[i]=line[i].chomp.split(" ")
13    hash1["#{line[i][0]}"]="#{line[i][1]}"
14    i+=1
15end
16
17#B→Cの辞書を作る
18while i<p+q
19    line[i]=line[i].chomp.split(" ")
20    hash2["#{line[i][0]}"]="#{line[i][1]}"
21    i+=1
22end
23
24#それぞれの辞書からキーとバリューを要素として取り出す
25h1=hash1.to_a
26h2=hash2.to_a
27
28#A→Cの辞書を作る
29hash_a={}
30a=0
31b=0
32l1=hash1.length
33l2=hash2.length
34
35while a<l1
36    if h1[a][1]==h2[b][0]
37        hash_a["#{h1[a][0]}"]="#{h2[b][1]}"
38        a+=1
39        b=0
40    else
41        b+=1
42    end
43end
44#A→CをAが小さい順に入れ替え、出力する
45c=hash_a.sort
46d=c.length
47while b<d
48    puts "#{c[b][0]} #{c[b][1]}"
49    b+=1
50end
51

入力された内容
50 50 50
19 12
5 44
18 36
16 13
39 29
32 33
48 13
11 47
9 50
4 9
35 27
14 42
25 25
22 8
44 26
23 27
8 14
45 1
28 18
2 38
42 20
17 2
1 14
27 12
34 26
37 39
49 42
24 37
21 7
15 3
41 10
26 14
3 29
6 17
10 1
20 50
47 40
7 22
43 19
40 25
31 5
46 5
12 6
13 14
38 38
33 41
50 16
30 1
36 39
29 24
8 24
44 40
10 30
20 9
23 38
12 31
43 37
4 9
41 25
49 12
48 41
47 10
45 20
38 15
24 40
11 16
9 47
32 13
31 11
14 48
29 41
13 36
16 13
39 44
35 25
34 31
50 39
22 6
28 27
1 4
3 7
25 7
40 3
46 33
26 17
7 16
37 48
5 46
2 26
19 17
33 27
15 39
21 32
17 19
6 34
36 12
27 47
18 5
42 9
30 15

出力された内容

1 48
10 4
11 10
12 34
13 48
14 9
15 7
16 36
17 26
18 12
19 31
2 15
20 39
21 16
22 24
23 47
24 48
25 7
26 48
27 31
28 5
29 40
3 41
30 4
31 46
32 27
33 25
34 17
35 47
36 44
37 44
38 15
39 41
4 47
40 7
41 30
42 9
43 17
44 17
45 4
46 46
47 3
48 36
49 9
5 40
50 13
6 19
7 6
8 48
9 39