Ngày DD tới, vào giờ HH:MM, toàn quân tổng tiến công!

Đó là quân lệnh từ sở chỉ huy cần được truyền tới tất cả các đơn vị chiến đấu. Tuấn làm việc trong bộ phận phụ trách thiết kế các module đảm bảo thông tin được truyền đi an toàn và chính xác. Thông tin được truyền đi sẽ gồm ba giai đoạn:

1. Mã hóa thông tin (encode): từ sở chỉ huy, thông tin (DD, HH, MM) sẽ được mã hóa thành một dãy bit;
2. Truyền tin (transmission): sử dụng những phương tiện thô sơ để truyền dãy bit tới các máy nhận ở các đơn vị;
3. Giải mã thông tin (decode): từ dãy bit nhận được, giải mã lại thông tin (DD, HH, MM).

Tuấn phụ trách thiết kế module 1 và 3 nhưng gặp rất nhiều khó khăn. Lý do chính là do kĩ thuật truyền tin thô sơ và phụ thuộc vào yếu tố kĩ năng của con người, nên không phải thông tin lúc nào cũng được truyền đi một cách hoàn toàn chính xác. Thông tin truyền đi có thể bị sai sót tối đa 1 bit. Vì vậy, yêu cầu của hệ thống mã hóa này phải có khả năng phát hiện lỗi, và tự sửa chữa sai sót. Nói cách khác, cho dù thông tin truyền đi có thể sai 1 bit nhưng vẫn phải tự khôi phục được.

Yêu cầu: Hãy giúp Tuấn thực hiện được công việc của mình.

Giao tiếp

Bạn cần viết hai hàm sau:

1. string encode (string message)

   Hàm nhận vào một xâu độ dài 8 có dạng DD HH:MM trong đó DD là một số nguyên trong đoạn ~[1,31]~, HH là một số nguyên trong đoạn ~[0,23]~ và MM là một số nguyên trong đoạn ~[0,59]~. Hàm cần trả về một xâu không quá 50 kí tự chỉ gồm các kí tự 0 hoặc 1 là xâu được mã hóa.

2. string decode (string encryptedMessage)

   Hàm nhận vào một xâu có độ dài không quá 50 kí tự, chỉ gồm các kí tự 0 hoặc 1. Hàm cần trả ra một xâu có độ dài 8 có định dạng giống xâu đầu vào của hàm encode là xâu đã được giải mã.

Làm bài

Các bạn có thể download file attack_public.zip chứa các file hỗ trợ làm bài. Trong đó:

• attack.cpp / attack.java là file các bạn cần làm việc và viết thuật toán mã hóa.
• stub.cpp / stub.java là file hỗ trợ các chức năng nhập xuất dữ liệu.
• compile_cpp.sh / compile_java.sh là script hỗ trợ việc biên dịch chương trình.

Bạn có thể làm các việc sau:

• Viết thuật toán mã hóa của bạn vào file attack.cpp hoặc attack.java. Các bạn có thể viết thêm các hàm phụ trợ khác.
• Biên dịch và thực thi bằng script được cung cấp như sau:
  • Vào thư mục chứa file attack.cpp hoặc attack.java, click chuột phải và chọn Open in Terminal.
  • Biên dịch file mã nguồn ra file thực thi bằng cách chạy lệnh ./compile_cpp.sh hoặc ./compile_java.sh.
  • Thực thi bằng cách chạy lệnh ./attack hoặc ./run_java.sh.
• File thực thi attack nhận dữ liệu vào từ dòng nhập chuẩn (stdin) ở một trong hai dạng:
  1. ENCODE DD HH MM
     • Ví dụ: ENCODE 1 12 5 với ý nghĩa gọi hàm encode("01 12:05")
  2. DECODE str
     • Ví dụ DECODE 00011101 với ý nghĩa gọi hàm decode("00011101")
  3. File thực thi sẽ in ra một xâu là kết quả của hàm tương ứng mà chương trình bạn chạy.

Ngoài ra, trong quá trình làm bài, các bạn có thể tự thay đổi file stub.cpp / stub.java để phục vụ theo cách nhập xuất dự liệu mà bạn muốn.

Nộp bài

Các bạn chỉ nộp file attack.cpp hoặc attack.java mà không nộp file nào khác.

Chấm bài

Bài của các bạn sẽ được chấm như sau. Ban giám khảo chuẩn bị một file hệ thống chấm (được gọi là manager).

• Chương trình manager sẽ gọi hàm encode của bạn với một bộ dữ liệu (DD, HH, MM) nào đó và thu được xâu encryptedMessage.
• Chương trình manager sẽ lặp lại các bước sau nhiều lần:
  • Sửa một bit hoặc không sửa bit nào tạo thành xâu receivedMessage.
  • Chương trình manager sẽ gọi hàm decode của bạn với đầu vào là xâu receivedMessage và so sánh kết quả thu được với bộ dữ liệu ban đầu.

Lưu ý rằng, những lần hàm encode và decode của bạn được gọi sẽ được chạy ở các tiến trình độc lập. Vì vậy, nếu hàm encode có sử dụng và lưu trữ dữ liệu vào các biến toàn cục, các dữ liệu này sẽ không tồn tại khi hàm decode được thực thi.

Chấm điểm

Với mỗi bộ dữ liệu, bạn sẽ không được điểm nếu:

• Tương tác sai quy cách (dữ liệu trả ra không đúng định dạng)
• Chạy sinh lỗi
• Chạy quá thời gian
• Xâu sau khi giải mã khác với xâu ban đầu

Gọi độ dài xâu mã hóa của bạn là ~L~, bạn sẽ nhận được điểm dựa trên độ tốt của ~L~ như sau:

Độ dài xâu mã hóa của bạn	Điểm của test
~1 \leq L \leq 21~	~100\%~
~L = 22~	~90\%~
~L = 23~	~80\%~
~24 \leq L \leq 25~	~60\%~
~26 \leq L \leq 30~	~40\%~
~31 \leq L \leq 35~	~30\%~
~36 \leq L \leq 40~	~20\%~
~41 \leq L \leq 50~	~10\%~

Một đất nước có ~n~ thành phố được đánh số từ 1 tới ~n~. Có ~m~ con đường cao tốc hai chiều được đánh số từ 1 tới ~m~, mỗi con đường nối trực tiếp hai thành phố phân biệt. Các con đường này đảm bảo từ một thành phố bất kỳ có thể đi đến một thành phố bất kỳ khác hoặc trực tiếp hoặc gián tiếp thông qua các các con đường khác. Giữa hai thành phố có thể có nhiều hơn một con đường nối trực tiếp.

Theo kế hoạch của Ban quản lý đường bộ, sắp tới mỗi đợt sẽ kiểm tra định kì một trong ~m~ con đường cao tốc. Trong thời gian kiểm tra người dân sẽ bị cấm ra, vào con đường này. Một con đường được xem là trọng yếu đối với hai thành phố ~u~ và ~v~ khi và chỉ khi mọi cách đi từ ~u~ đến ~v~ đều phải đi qua con đường đó (không được phép đi qua con đường đang kiểm tra). Lưu ý là nếu không có đường đi nào từ ~u~ đến ~v~ thì đối với hai thành phố này không có con đường nào là trọng yếu. Công ty BMAP quyết định xây dựng một phần mềm tra cứu giúp người dân nơi đây tìm xem, với một cặp thành phố ~(u,v)~, nếu một con đường được chọn để kiểm tra thì sẽ có những con đường nào là trọng yếu trong số ~m-1~ con đường còn lại.

Yêu cầu: Bạn hãy giúp công ty BMAP đưa ra kết quả tra cứu cho người dân.

Input

• Dòng đầu tiên chứa 2 số nguyên dương ~n~ và ~m~ (~n,m \geq 2~);
• Dòng thứ ~i~ trong số ~m~ dòng tiếp theo (~1\leq i \leq m~) chứa 2 số nguyên dương ~u~ và ~v~ (~u,v \leq n; u\neq v~) cho biết đường cao tốc thứ ~i~ nối trực tiếp hai thành phố ~u~ và ~v~;
• Dòng tiếp theo chứa một số nguyên dương ~q~ là số lượng truy vấn;
• Dòng thứ ~j~ trong số ~q~ dòng tiếp theo (~1\leq j \leq q~) chứa 3 số nguyên dương ~k~, ~u~ và ~v~ (~k \leq m; u,v \leq n; u\neq v~) mô tả truy vấn thứ ~j~ nếu con đường ~k~ đang trong đợt kiểm tra thì cần tìm số con đường trọng yếu giữa hai thành phố ~u~ và ~v~.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

In ra ~q~ dòng, dòng thứ ~j~ (~1\leq j\leq q~) ghi một số duy nhất là tổng số con đường trọng yếu tìm được đối với truy vấn thứ ~j~ trong dữ liệu vào.

Giới hạn

• Subtask 1 (15 điểm): ~n,m,q\leq 500~;
• Subtask 2 (15 điểm): ~n,m,q\leq 5000~;
• Subtask 3 (20 điểm): ~n,m,q\leq 200000~, ~k=1~ trong mọi truy vấn;
• Subtask 4 (20 điểm): ~n,m,q\leq 200000~, ~u=1~ và ~v=2~ trong mọi truy vấn;
• Subtask 5 (30 điểm): ~n,m,q\leq 200000~.

Sample input

4 5
1 2
1 3
2 3
2 4
3 4
3
1 1 4
3 1 4
4 1 4

Sample output

1
0
1

Hình minh họa ví dụ