In a case where a public key of a communication device is obtained, a terminal device may send a first request signal in which the public key is used to the communication device and execute a first-type communication in conformity with the first communication scheme with the communication device. The first-type communication may include sending first connection information for establishing a first wireless connection between the communication device and the access point to the communication device. In a case where the first-type communication has been failed, the terminal device may send a second request signal to the communication device and execute a second-type communication in conformity with the second communication scheme with the communication device. The second-type communication may include communicating second connection information for establishing a second wireless connection between the terminal device and the communication device with the communication device.